package ch8recursion;

import java.util.ArrayList;
import java.util.List;

public class Ex4 {

	static List<String> permutations(String input) {
		List<String> result = new ArrayList<>();
		if (input.length() == 0) {
			result.add("");
		}
		else {
			char head = input.charAt(0);
			List<String> subs = permutations(input.substring(1));
			for (String sub : subs) {
				for (int i=0; i<sub.length(); i++) {
					StringBuilder sb = new StringBuilder(sub);
					sb.insert(i, head);
					result.add(sb.toString());
				}
				result.add(sub+head);
			}
		}
		return result;
	}
	
	public static void main(String ...strings ) {
		List<String> permutations = permutations("abc");
		int a=0;
	}
	
}
